#include "main/utils.h"
using namespace std;

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
      int n = nums.size();
      vector<int> min_vec(n, 0);
      vector<int> max_vec(n, 0);
      min_vec[0] = nums[0];
      max_vec[n - 1] = nums[n - 1];
      for (int i = 1; i < n; ++i) {
        if (nums[i] < min_vec[i - 1]) {
          min_vec[i] = nums[i];
        } else {
          min_vec[i] = min_vec[i - 1];
        }
      }
      for (int i = n - 2; i >= 0; --i) {
        if (nums[i] > max_vec[i + 1]) {
          max_vec[i] = nums[i];
        } else {
          max_vec[i] = max_vec[i + 1];
        }
      }
      for (int i = 1; i < n - 1; ++i) {
        if (nums[i] > min_vec[i - 1] && nums[i] < max_vec[i + 1]) {
          return true;
        }
      }
      return false;
    }

    bool increasingTriplet1(vector<int>& nums) {
      int first = nums[0];
      int second = INT_MAX;
      for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > second) {
          return true;
        } else if (nums[i] > first && nums[i] <= second){
          second = nums[i];
        } else if (nums[i] < first) {
          first = nums[i];
        }
      }
      return false;
    }
};

int main() {
  vector<int> nums = {20, 100, 10, 12, 5, 13};
  Solution su;
  cout << su.increasingTriplet(nums) << endl;
  cout << su.increasingTriplet1(nums) << endl;

  return 0;
}
